We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers.

In this paper we study a notion of HL-extension for a structure in a finite relational language $\mathcal {L}$. We give a description of all finite minimal HL-extensions of a given finite $\mathcal {L}$ -structure. In addition, we study a group-theoretic property considered by Herwig–Lascar and show that it is closed under taking free products. We also introduce notions of coherent extensions and ultraextensive $\mathcal {L}$ -structures and show that every countable $\mathcal {L}$ -structure can be extended to a countable (...) ultraextensive structure. Finally, it follows from our results that the automorphism group of any countable ultraextensive $\mathcal {L}$ -structure has a dense locally finite subgroup. (shrink)

§ 1. Introduction. In this communication we present some recent results on the classification of Polish metric spaces up to isometry and on the isometry groups of Polish metric spaces. A Polish metric space is a complete separable metric space.Our first goal is to determine the exact complexity of the classification problem of general Polish metric spaces up to isometry. This work was motivated by a paper of Vershik [1998], where he remarks : “The classification of Polish spaces up to (...) isometry is an enormous task. More precisely, this classification is not ‘smooth’ in the modern terminology.” Our Theorem 2.1 below quantifies precisely the enormity of this task.After doing this, we turn to special classes of Polish metric spaces and investigate the classification problems associated with them. Note that these classification problems are in principle no more complicated than the general one above. However, the determination of their exact complexity is not necessarily easier.The investigation of the classification problems naturally leads to some interesting results on the groups of isometries of Polish metric spaces. We shall also present these results below.The rest of this section is devoted to an introduction of some basic ideas of a theory of complexity for classification problems, which will help to put our results in perspective. Detailed expositions of this general theory can be found, e.g., in Hjorth [2000], Kechris [1999], [2001]. (shrink)

Strengthening a theorem of D.W. Kueker, this paper completely characterizes which countable structures do not admit uncountable L ω 1 ω -elementarily equivalent models. In particular, it is shown that if the automorphism group of a countable structure M is abelian, or even just solvable, then there is no uncountable model of the Scott sentence of M. These results arise as part of a study of Polish groups with compatible left-invariant complete metrics.

We consider the equivalence relations on induced by the Banach subspaces. We show that if, then there is no Borel reduction from the equivalence relation, where X is a Banach space, to.

Strengthening known instances of Vaught Conjecture, we prove the Glimm-Effros dichotomy theorems for countable linear orderings and for simple trees. Corollaries of the theorems answer some open questions of Friedman and Stanley in an L ω 1ω -interpretability theory. We also give a survey of this theory.

We prove a number of results about countable Borel equivalence relations with forcing constructions and arguments. These results reveal hidden regularity properties of Borel complete sections on certain orbits. As consequences they imply the nonexistence of Borel complete sections with certain features.

We prove that the strong Martin conjecture is false. The counterexample is the first-order theory of infinite atomic Boolean algebras. We show that for this class of Boolean algebras, the classification of their (ω + ω)-elementary theories can be reduced to the classification of the elementary theories of their quotient algebras modulo the Frechet ideals.

We study the notion of polynomial-time relation reducibility among computable equivalence relations. We identify some benchmark equivalence relations and show that the reducibility hierarchy has a rich structure. Specifically, we embed the partial order of all polynomial-time computable sets into the polynomial-time relation reducibility hierarchy between two benchmark equivalence relations Eλ and id. In addition, we consider equivalence relations with finitely many nontrivial equivalence classes and those whose equivalence classes are all finite.

In this paper we define and study conditional problems and their degrees. The main result is that the class of conditional degrees is a lattice extending the ordinary Turing degrees and it is dense. These properties are not shared by ordinary Turing degrees. We show that the class of conditional many-one degrees is a distributive lattice. We also consider properties of semidecidable problems and their degrees, which are analogous to r.e. sets and degrees.

Let E be a coanalytic equivalence relation on a Polish space X and (A n ) n∈ω a sequence of analytic subsets of X. We prove that if lim sup n∈K A n meets uncountably many E-equivalence classes for every K ∈ [ω] ω , then there exists a K ∈ [ω] ω such that ⋂ n∈K A n contains a perfect set of pairwise E-inequivalent elements.

We investigate diagonal actions of Polish groups and the related intersection operator on closed subgroups of the acting group. The Borelness of the diagonal orbit equivalence relation is characterized and is shown to be connected with the Borelness of the intersection operator. We also consider relatively tame Polish groups and give a characterization of them in the class of countable products of countable abelian groups. Finally an example of a logic action is considered and its complexity in the Borel reducbility (...) hierarchy determined. (shrink)

We define some variations of the Scott rank for countable models and obtain some inequalities involving the ranks. For mono-unary algebras we prove that the game rank of any subtree does not exceed the game rank of the whole model. However, similar questions about linear orders remain unresolved.